//
//  list_remove_node.hpp
//  cpp_algorithm
//
//  Created by 李贺 on 2021/11/26.
//

#ifndef list_remove_node_hpp
#define list_remove_node_hpp

#include <stdio.h>
#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL) {
    }
};

class Solution_list_remove {
    
public:
    //1->4->2->4, 移除4
    ListNode * removeElement(ListNode * head, int val) {
        
        
        // 移除从头结点就是val的node
        while (head != NULL && head->val == val) {
            ListNode *temp = head;
            head = head->next;
            delete temp;
        }
        

        ListNode *current_cursor = head;
        ListNode *pre_cursor = current_cursor;
        
        while (current_cursor != NULL) {
            if (current_cursor->val == val) {
                ListNode * temp = current_cursor;
                pre_cursor->next = current_cursor->next;
                current_cursor = current_cursor->next;
                delete temp;
            } else {
                pre_cursor = current_cursor;
                // 向后滑动
                current_cursor = current_cursor->next;
            }
        }
        
        return head;
    }
    
    ListNode* removeElements1(ListNode* head, int val) {
            ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
            dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
            ListNode* cur = dummyHead;
            while (cur->next != NULL) {
                if(cur->next->val == val) {
                    ListNode* tmp = cur->next;
                    cur->next = cur->next->next;
                    delete tmp;
                } else {
                    cur = cur->next;
                }
            }
            head = dummyHead->next;
            delete dummyHead;
            return head;
        }
    
    void test() {
        ListNode *node1 = new ListNode(1);
        ListNode *node2 = new ListNode(4);
        ListNode *node3 = new ListNode(2);
        ListNode *node4 = new ListNode(4);
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = NULL;
        ListNode *remainNode = removeElement(node1, 4);
        ListNode *temp = remainNode;
        while (temp != NULL) {
            cout << temp->val << "\n";
            temp = temp->next;
        }
    }
};

#endif /* list_remove_node_hpp */
